关键词: 动态混合流水车间调度, 有限运输能力, 阶段分解, 拉格朗日松弛, 动态规划, 机器不可用时间段

Abstract: To improve the inventory and energy consumption of work in process,the dynamic hybrid flowshop scheduling with transportation consideration in practical manufacturing circumstances of steel enterprises was studied.Transporters were viewed as virtual machines to transform the original problem into dynamic Hybrid FlowShop (HFS) scheduling problem of one without transportation but with job-dependent unavailable time windows of machines at even stages,in which the unavailable time of machines depended on delivery workpieces.The mathematical model for transformed problem was constructed,and Lagrangian Relaxation (LR) algorithm based on stage-decomposition was solved.In this algorithm,the precedence constraints were relaxed into objective function,and LR problem was decomposed in multiple stage-level sub-problems.Thus a dynamic programming algorithm was designed to solve these parallel identical machine scheduling sub-problems with any job weight and unavailable time windows of machines.Numerical results on problems with different scale showed that the designed LR algorithm could obtain acceptable near-optimal solutions within a shorter computational time.

Key words: dynamic hybrid flowshop scheduling, finite transportation capacity, stage decomposition, Lagrangian relaxation, dynamic programming, unavailable time windows of machines